package com.sicheng.lc.周赛.分类.前缀和or差分数组;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/1 22:22
 */
public class 分组得分最高的所有下标 {
    //https://leetcode.cn/problems/all-divisions-with-the-highest-score-of-a-binary-array/
    public List<Integer> maxScoreIndices(int[] nums) {
        ArrayList<Integer> res = new ArrayList<>();
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int max = Math.max(sum, nums.length - sum);
        int preSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(max, i - preSum + sum - preSum);
            preSum += nums[i];
        }

        preSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (i - preSum + sum - preSum == max)
                res.add(i);
            preSum += nums[i];
        }
        if (sum == max)
            res.add(0);
        if (nums.length - sum == max)
            res.add(nums.length);

        return res;

    }
}
